/* text.h
Copyright (c) 2008 Michael Zahniser
Please note the license terms (MIT license) at the end of this document.

Header file for the text class, which represents a text buffer.

TODO: Move mark anchors into a shared pointer that all marks keep a copy of.
Until then, deleting the text before deleting all marks is an error.
*/

#ifndef __MZ_TEXT_H__
#define __MZ_TEXT_H__

#include <iterator>
#include <ostream>
#include <istream>
#include <list>

using std::ptrdiff_t;



class text {
public:
	// A mark is a fixed position in the text. Marks are not invalidated
	// by any changes to the text (unless those changes delete the marks).
	class mark;

	// Constant and mutable iterators over a text object.
	class iterator;
	class const_iterator;


public:
	// Default constructor.
	// Allocates an empty text buffer of the MINIMUM_SIZE.
	text();
	// Constructor, specifying a string and optionally its length.
	// If length < MINIMUM_SIZE, creates a gap at the end of the string.
	text(const char *str, size_t length = 0);
	// Copy constructor.
	text(const text &t);
	// Destructor.
	~text();

	// Make this a deep copy of the given text object.
	text &operator=(const text &t);
	// Copy the given string into this text object.
	text &operator=(const char *str);

	// Copy the given string into this text. If you don't want to
	// specify the string length, use operator=, above.
	// If length < MINIMUM_SIZE, creates a gap at the end of the string.
	void assign(const char *str, size_t length);
	// Swap the data in two different text objects.
	void swap(text &text);
	// Use the given buffer. When this function is called, text
	// becomes the owner of the given array, which must have been
	// allocated usng new[].
	void use_buffer(char *str, int length);

	// Get iterators to the text.
	iterator begin();
	const_iterator begin() const;
	iterator end();
	const_iterator end() const;

	// Convert an iterator into a mark.
	mark make_mark(const_iterator it) const;
	// Convert a mark into an iterator.
	iterator make_iterator(mark mk);
	const_iterator make_iterator(mark mk) const;
	// Convert the given const_iterator into a mutable iterator.
	// This can only be done from non-const member functions.
	iterator unconst(const_iterator it);
	
	// Get the number of bytes in the text.
	size_t size() const;
	// Clear all data.
	void clear();
	// Check if any data is contained in this text.
	bool empty() const;
	// Reserve the given number of bytes.
	void reserve(size_t bytes);
	// Get the number of bytes reserved.
	size_t capacity() const;

	// Insert the given character or text to the left of the iterator.
	// Returns the new position of the iterator.
	// Invalidates all iterators except the one returned.
	iterator insert(const char *str, size_t length, iterator it);
	iterator insert(const char *str, iterator it);
	iterator insert(char c, iterator it);
	// Delete the character to the left of the iterator.
	// Does nothing if the given iterator is at the beginning.
	// Returns the new position of the iterator.
	// Invalidates all iterators except the one returned.
	iterator backspace(iterator it);
	// Delete the characters between the given iterators.
	// Returns an iterator to where those characters used to be.
	// Invalidates all iterators except the one returned.
	iterator erase(iterator first, iterator last);
	// Delete the character to the right of the iterator.
	// Does nothing if the given iterator is at the end.
	iterator erase(iterator it);
	// A replace (like std::string provides) is just an erase followed
	// by an insert, and because of the gap there's no efficiency gained
	// by doing it in one step instead of two. So for now I won't bother
	// providing a replace() function in the interface.
	
	// Search the string for the first instance of the given string.
	// These functions are considerably faster than using the STL find() or search()
	// on an iterator (which must check for the gap every time it is incremented).
	// This version specifies the search string length.
	const_iterator find(const char *str, size_t length, const_iterator it) const;
	iterator find(const char *str, size_t length, iterator it);
	// Search the string for the first instance of the given string.
	const_iterator find(const char *str, const_iterator it) const;
	iterator find(const char *str, iterator it);
	// Search the string for the given character.
	const_iterator find(char c, const_iterator it) const;
	iterator find(char c, iterator it);
	
	// Search backward for the first instance of the given string.
	// These functions assume that the given iterator is dereferenceable - 
	// in particular, it may not be the end iterator.
	// This version specifies the search string length.
	const_iterator rfind(const char *str, size_t length, const_iterator it) const;
	iterator rfind(const char *str, size_t length, iterator it);
	// Search backward for the first instance of the given string.
	const_iterator rfind(const char *str, const_iterator it) const;
	iterator rfind(const char *str, iterator it);
	// Search backward for the given character.
	const_iterator rfind(char c, const_iterator it) const;
	iterator rfind(char c, iterator it);

	// Formatted IO:
	friend std::ostream &operator<<(std::ostream &out, const text &t);
	// Read until the end of the input.
	// If the input size is known in advance, call reserve() first to allocate
	// enough space to hold it.
	friend std::istream &operator>>(std::istream &in, text &t);

	// Overloads to provide default arguments.
	const_iterator find(const char *str, size_t length) const { return find(str, length, begin()); }
	iterator find(const char *str, size_t length) { return find(str, length, begin()); }
	const_iterator find(const char *str) const { return find(str, begin()); }
	iterator find(const char *str) { return find(str, begin()); }
	const_iterator find(char c) const { return find(c, begin()); }
	iterator find(char c) { return find(c, begin()); }
	const_iterator rfind(const char *str, size_t length) const { return rfind(str, length, end()); }
	iterator rfind(const char *str, size_t length) { return rfind(str, length, end()); }
	const_iterator rfind(const char *str) const { return rfind(str, end()); }
	iterator rfind(const char *str) { return rfind(str, end()); }
	const_iterator rfind(char c) const { return rfind(c, end()); }
	iterator rfind(char c) { return rfind(c, end()); }
	
	void printMarks(std::ostream &out) const
	{
		for(std::list<MarkAnchor>::const_iterator it = marks.begin(); it != marks.end(); ++it)
			out << it->count << ":" << it->pos << "\t";
		out << std::endl;
	}


private:
	// Initialize the mark list.
	void init_marks();
	// Move the gap to the given position. Update the iterator to point to
	// the end of the gap. Also increase the size of the gap by the given amount.
	void move_gap(iterator &it, size_t sizeIncrease = 0);
	
	
private:
	char *buffer;
	char *gap;
	char *gapEnd;
	char *bufferEnd;

	// The data structure for marks.
	class MarkAnchor {
	public:
		MarkAnchor(ptrdiff_t pos) : pos(pos), count(0) {}

		// If pos < 0, this is an invalid mark.
		ptrdiff_t pos;
		size_t count;
	};

	// A list of all marks that must be updated when the gap moves.
	mutable std::list<MarkAnchor> marks;
	// This list entry represents the current gap position.
	std::list<MarkAnchor>::iterator gapMark;
	// Any marks after this point are not valid anymore, but are still in the list
	// because the mark objects using them still exist.
	std::list<MarkAnchor>::iterator unMark;


private:
	// Always allocate at least a kilobyte for new text objects.
	static const size_t MINIMUM_SIZE = 1024;


public:
	// This class represents a mark - a position record that stays valid regardless
	// of changes to the text, unless the marked position itself is deleted.
	class mark {
	public:
		mark();
		mark(const mark &mk);
		~mark();

		mark &operator=(const mark &mk);
		// Check whether this mark is valid.
		bool operator!() const;
		
		// Comparison. This is a strict weak ordering. If the mark is invalid, any
		// comparison to it will return false.
		bool operator==(const mark &mk) const;
		bool operator<(const mark &mk) const;

	private:
		void retain();
		void release();

		// This constructor is accessible to the text class.
		mark(std::list<MarkAnchor> &marks, std::list<MarkAnchor>::iterator it);
		friend class text;

	private:
		std::list<MarkAnchor>::iterator it;
		std::list<MarkAnchor> *marks;
	};


public:
	// Below are the nested classes used by this class.

	// There are separate classes for contant and mutable iterators.
	// Define their common functionality in a template base class.
	template<class Me, class Ptr, class Ref>
	class _it : public std::iterator<std::random_access_iterator_tag, char, ptrdiff_t, Ptr, Ref> {
	public:
		_it();
		// Use the default copy constructor and assignment operator.
		// It won't be any slower, and it may be faster than writing my own.

		void swap(_it &it);

		bool operator==(const _it &it) const;
		bool operator!=(const _it &it) const;

		bool operator<(const _it &it) const;
		bool operator<=(const _it &it) const;
		bool operator>(const _it &it) const;
		bool operator>=(const _it &it) const;

		// Check if the iterator is initialized.
		bool operator!() const;

		Ref operator*() const;
		Ptr operator->() const;

		Me &operator++();
		Me operator++(int);
		Me &operator--();
		Me operator--(int);

		Me operator+(ptrdiff_t n) const;
		template<class, class, class>
		friend Me operator+(ptrdiff_t n, const _it &it);
		Me &operator+=(ptrdiff_t n);
		Me operator-(ptrdiff_t n) const;
		template<class, class, class>
		friend Me operator-(ptrdiff_t n, const _it &it);
		Me &operator-=(ptrdiff_t n);

		ptrdiff_t operator-(const _it &it) const;

		Ref operator[](ptrdiff_t n) const;

	protected:
		_it(Ptr p, Ptr gap, Ptr gapEnd);

	protected:
		Ptr p;
		Ptr gap;
		Ptr gapEnd;

	private:
		Me &promote();
	};

private:
	typedef _it<iterator, char *, char &> m_it;
public:
	class iterator : public m_it {
	public:
		iterator();
		// Use the default copy constructor and assignment operator.
		// It won't be any slower, and it may be faster than writing my own.

	private:
		// Private constructor.
		iterator(char *p, char *gap, char *gapEnd);
		friend class text;
		// Allow const_iterator to access my data to convert me into one of it.
		friend class text::const_iterator;
	};

private:
	typedef _it<const_iterator, const char *, const char &> c_it;
public:
	class const_iterator : public c_it {
	public:
		const_iterator();
		// Convert from an iterator to a const_iterator.
		const_iterator(const text::iterator &it);
		// Use the default copy constructor and assignment operator.
		// It won't be any slower, and it may be faster than writing my own.

	private:
		// Private constructor.
		const_iterator(const char *p, const char *gap, const char *gapEnd);
		friend class text;
	};
};



// Following are the function definitions for text::_it.

// Default constructor:
template<class Me, class Ptr, class Ref>
text::_it<Me, Ptr, Ref>::_it()
	: p(NULL), gap(NULL), gapEnd(NULL)
{
}



// swap():
template<class Me, class Ptr, class Ref>
void text::_it<Me, Ptr, Ref>::swap(_it &it)
{
	_it temp = *this;
	*this = it;
	it = temp;
}



// operator==():
template<class Me, class Ptr, class Ref>
bool text::_it<Me, Ptr, Ref>::operator==(const _it &it) const
{
	return (p == it.p);
}



// operator!=():
template<class Me, class Ptr, class Ref>
bool text::_it<Me, Ptr, Ref>::operator!=(const _it &it) const
{
	return !(*this == it);
}



// operator<():
template<class Me, class Ptr, class Ref>
bool text::_it<Me, Ptr, Ref>::operator<(const _it &it) const
{
	return (p < it.p);
}



// operator<=():
template<class Me, class Ptr, class Ref>
bool text::_it<Me, Ptr, Ref>::operator<=(const _it &it) const
{
	return !(it < *this);
}



// operator>():
template<class Me, class Ptr, class Ref>
bool text::_it<Me, Ptr, Ref>::operator>(const _it &it) const
{
	return (it < *this);
}



// operator>=():
template<class Me, class Ptr, class Ref>
bool text::_it<Me, Ptr, Ref>::operator>=(const _it &it) const
{
	return !(*this < it);
}



// operator!():
template<class Me, class Ptr, class Ref>
bool text::_it<Me, Ptr, Ref>::operator!() const
{
	return !p;
}



// operator*():
template<class Me, class Ptr, class Ref>
Ref text::_it<Me, Ptr, Ref>::operator*() const
{
	return *p;
}



// operator->():
template<class Me, class Ptr, class Ref>
Ptr text::_it<Me, Ptr, Ref>::operator->() const
{
	return &**this;
}



// operator++():
template<class Me, class Ptr, class Ref>
Me &text::_it<Me, Ptr, Ref>::operator++()
{
	++p;
	if(p == gap)
		p = gapEnd;
	return promote();
}



// operator++() postfix:
template<class Me, class Ptr, class Ref>
Me text::_it<Me, Ptr, Ref>::operator++(int)
{
	Me it = *this;
	++(*this);
	return it;
}



// operator--():
template<class Me, class Ptr, class Ref>
Me &text::_it<Me, Ptr, Ref>::operator--()
{
	if(p == gapEnd)
		p = gap;
	--p;
	return promote();
}



// operator--() postfix:
template<class Me, class Ptr, class Ref>
Me text::_it<Me, Ptr, Ref>::operator--(int)
{
	Me it = *this;
	--(*this);
	return it;
}



// operator+():
template<class Me, class Ptr, class Ref>
Me text::_it<Me, Ptr, Ref>::operator+(ptrdiff_t n) const
{
	_it result = *this;
	return result += n;
}



// operator+() global:
template<class Me, class Ptr, class Ref>
Me operator+(ptrdiff_t n, const text::_it<Me, Ptr, Ref> &it)
{
	return (it - n);
}



// operator+=():
template<class Me, class Ptr, class Ref>
Me &text::_it<Me, Ptr, Ref>::operator+=(ptrdiff_t n)
{
	// Each of these functions handles one direction of travel.
	if(n < 0)
		return (*this -= -n);

	// We only have to worry about crossing the gap if we're
	// currently to the left of it.
	bool wasBeforeGap = (p < gap);
	p += n;

	// If we crossed the beginning of the gap, shift the pointer
	// by the width of the gap to skip across it.
	if(wasBeforeGap && p >= gap)
		p += (gapEnd - gap);

	return promote();
}



// operator-():
template<class Me, class Ptr, class Ref>
Me text::_it<Me, Ptr, Ref>::operator-(ptrdiff_t n) const
{
	_it result = *this;
	return result -= n;
}



// operator-() global:
template<class Me, class Ptr, class Ref>
Me operator-(ptrdiff_t n, const text::_it<Me, Ptr, Ref> &it)
{
	return (it - n);
}



// operator-=():
template<class Me, class Ptr, class Ref>
Me &text::_it<Me, Ptr, Ref>::operator-=(ptrdiff_t n)
{
	// Each of these functions handles one direction of travel.
	if(n < 0)
		return (*this += -n);

	// We only have to worry about crossing the gap if we're
	// currently to the right of it.
	bool wasAfterGap = (p >= gap);
	p -= n;

	// If we crossed the end of the gap, shift the pointer
	// by the width of the gap to skip across it.
	if(wasAfterGap && p < gapEnd)
		p -= (gapEnd - gap);

	return promote();
}



// operator-() ptrdiff:
template<class Me, class Ptr, class Ref>
ptrdiff_t text::_it<Me, Ptr, Ref>::operator-(const _it &it) const
{
	// Assume the pointers belong to the same text.
	// Otherwise, this value has no real meaning.
	ptrdiff_t diff = p - it.p;

	// If both pointers are on the same side of the gap, just take
	// the difference between them. Assume p is not in [gap, gapEnd).
	if((p < gap) == (it.p < gap))
		return diff;

	// The pointers straddle the gap. Get the width of the gap.
	ptrdiff_t gapWidth = gapEnd - gap;

	// Subtract the gap width from the absolute difference.
	return (diff < 0) ? diff + gapWidth : diff - gapWidth;
}



// operator[]():
template<class Me, class Ptr, class Ref>
Ref text::_it<Me, Ptr, Ref>::operator[](ptrdiff_t n) const
{
	return *(*this + n);
}



// Constructor:
template<class Me, class Ptr, class Ref>
text::_it<Me, Ptr, Ref>::_it(Ptr p, Ptr gap, Ptr gapEnd)
	: p(p), gap(gap), gapEnd(gapEnd)
{
}



// promote():
template<class Me, class Ptr, class Ref>
Me &text::_it<Me, Ptr, Ref>::promote()
{
	// NOTE: This only works if Me is derived from _it.
	// But that's a safe assumption to make, here.
	return *reinterpret_cast<Me *>(this);
}



#endif



/* Copyright (c) 2008 Michael Zahniser

Permission is hereby granted, free of charge, to any person
obtaining a copy of this software and associated documentation
files (the "Software"), to deal in the Software without
restriction, including without limitation the rights to use,
copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following
conditions:

The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE. */

